package algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 动态规划_最长递增子序列
给定数列A1,A2,...An，求最长递增子序列:
 在求以Ai为末元素的最长递增子序列时，找到所有在Ai前面且小于Ai的元素Aj，即j<i且Aj<Ai，如果这样的元素存在，
 那么对所有Aj,都有一个以Aj为末元素的最长递增子序列的长度S(j)，把其中最大的S(j)选出来，那么S(i)就等于最大的S(j)加上1，
 即以Ai为末元素的最长递增子序列，等于以使S(j)最大的那个Aj为末元素的递增子序列最末再加上Ai；
 如果这样的元素不存在，那么Ai自身构成一个长度为1的以Ai为末元素的递增子序列。
 阶段i:以第i个数为末元素
 状态S[i]:以第i个数为末元素的可能递增序列长度
 转移方程：S[i+1]=max{S[i]}+1
 
    7

    3   8

    8   1   0

    2   7   4   4

    4   5   2   6   5
    数值相加，只能往左或右，找出最大值
    初始状态: 4 5 2 6 5
   状态转移：挑大的数字往上累加并记录，一直到最顶层
 *
 *
动态规划： 
 把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决(数字三角形例）。
 子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。
步骤：
确定一些初始状态（边界状态）的值
确定状态转移方程

例子：
初始状态：1 0 0 0
状态转移方程：从第二个开始，i对应len为索引小于它、值小于它且len最大再加1
 */
public class DTGH {

	public static void main(String[] args) {
//		int[] nums = {7, 9, 5, 3, 6, 4, 7, 9, 3, 0};
		int[] nums = {5, 6, 4, 7};
		f(nums);
	}
	
	public static void f(int[] nums) {
		List<A> aList = new ArrayList<A>();
		for(int i=0; i<nums.length; i++) {
			if(i == 0) {
				aList.add(new A(nums[i], 1));
			} else {
				aList.add(new A(nums[i], 0));
			}
		}
		for(A a : aList) {
			System.out.print(a.num + " ");
		}
		System.out.print("\n");
		
		//充分利用前面的结果。索引小于i的，值也小于i的，这种数据的结果可以利用。
		//遍历索引小于i的，值也小于i的，找出最大的len，加1，即为当前的len
		for(int i=1; i<aList.size(); i++) {
			int subMaxLength = 0;
			for(int j=0; j<i; j++) {
				if(aList.get(j).num < aList.get(i).num && aList.get(j).len > subMaxLength) {
					subMaxLength = aList.get(j).len;
				}
			}
			aList.get(i).len = subMaxLength + 1; //序列肯定包括它自身，所以加1 
		}
		
		for(A a : aList) {
			System.out.print(a.num + " ");
		}
		System.out.print("\n");
		for(A a : aList) {
			System.out.print(a.len + " ");
		}
	}
	
	public static class A {
		int num;
		int len;
		
		A(int n, int l) {
			num = n;
			len = l;
		}
	}

}
